package org.zjt.ds;

import scala.collection.immutable.Set;

import java.util.Arrays;
import java.util.Objects;

/**
 * @author juntao.zhang
 * @version V1.0
 * @Description: 归并排序。时间复杂度  N * (LOG 2 N)
 * @Package org.zjt.ds
 * @date 2018/4/22 16:59
 */
public class MergeSort {

    public static void main(String[] args) {

        Integer[] data = new Integer[]{1,12,323,2,54,341,4,8,9889};
        doMergeSort(data);
        Arrays.stream(data).forEach(System.err::println);
    }



    private static Integer[] newData ;
    public static synchronized Integer[] doMergeSort(Integer[] data){
        newData = new Integer[data.length];
        doMergeSort(data,0,data.length-1);
        return newData;
    }

    /**
     * 将数组拆分为两个数组，fork 。
     * join合并两个数组，逐级比较。
     * @param data
     * @param startIndex
     * @param endIndex
     */
    public static void doMergeSort(Integer[] data,int startIndex,int endIndex) {
        if (Objects.equals(startIndex, endIndex) )return;
        else{

            // 将数组拆分成两个数组   fork
            int mid = (startIndex + endIndex) /2;
            doMergeSort(data,startIndex,mid);
            doMergeSort(data,mid +1 ,endIndex);

            // 合并拆分后的数组   join
            doMerge(data,startIndex,mid + 1,endIndex);
        }
    }

    private static void doMerge(Integer[] data, int startIndex, int midIndex, int endIndex) {
        int start = startIndex;
        int newIndex = 0 ;
        int mid = midIndex;

        // 合并两个数组，
        while (start < midIndex && mid <= endIndex){
            if (data[start] <= data[mid]){
                newData[newIndex ++] = data[start ++];
            }else{
                newData[newIndex ++] = data[mid ++];
            }
        }

        //前面数组：将两个数组比较，数组剩余的内容保存
        while (start < midIndex )
            newData[newIndex ++] = data[start ++];

        //后面数组
        while (mid <= endIndex)
            newData[newIndex ++] = data[mid ++];

        //将保存数组的newData数组中的元素保存到原来数组中。
        for (int i = 0; i < newIndex; i++) {
            data[startIndex + i] = newData[i];
        }
    }
}
